package class06

import "math"

/*
	返回最大异或和的子数组
	思路：
		O(N^3)
			以每个位置为结尾，然后尝试所有的子数组，求出亦或和，找到最大值

		O(N^2)
			对前一种方案的优化，a ^ b = c  => a = b ^ c
			[0..i] 的疑惑和为 sum
			[0..j] [j+1...i] 两段的亦或和分别为 eor1, eor2
			sum = eor1 ^ eor2
			想求[j+1...i]的亦或和，测试不需要遍历 j+1...i，可以直接求得 eor2[j+1...i] = sum ^ eor1[0..j]

		O(N)
			将异或和数组，组织成前缀树，然后，沿路使用01构建，提供两个方法add()添加亦或和, maxXor()当前异或和为入参，返回最大亦或和
*/
func MaxXorSubarray1(arr []int) int {
	eorSum := make([]int, len(arr))
	eorSum[0] = arr[0]
	for i:=1; i<len(arr); i++ {
		eorSum[i] = arr[i] ^ eorSum[i-1]
	}
	var ans    int
	var j2iXor int
	for i:=0; i<len(arr); i++ { // 遍历以每个位置为结尾
		for j:=0; j<=i; j++ {   // 每个位置为结尾的子串遍历
			// j..i 的亦或结果
			if j == 0 {
				j2iXor = eorSum[i]
			} else {
				j2iXor = eorSum[i] ^ eorSum[j-1]
			}
			ans = max(ans, j2iXor)
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func MaxXorSubarray2(arr []int) int {
	var eor int
	xt := XorTire{&TireNode{nexts: [2]*TireNode{}}}
	xt.Add(0)
	ans := math.MinInt
	for i:=0; i<len(arr); i++ {
		eor = eor ^ arr[i]
		xt.Add(eor)
		ans =  max(ans, xt.MaxXor(eor))
	}
	return ans
}

type TireNode struct{
	nexts [2]*TireNode
}

type XorTire struct {
	head *TireNode
}

func (xt *XorTire) Add(xorSum int) {
	cur := xt.head
	for move := 63; move>=0; move-- {
		path :=  (xorSum >> move) & 1
		if cur.nexts[path] == nil {
			cur.nexts[path] = &TireNode{nexts: [2]*TireNode{}}
		}
		cur = cur.nexts[path]
	}
}

func (xt *XorTire) MaxXor(xorSum int) int {
	var ans int
	var best int
	cur := xt.head
	for move:=63; move>=0; move-- {
		path := (xorSum>>move) & 1
		if move == 63 {
			best = path
		} else {
			best = path ^ 1
		}
		if cur.nexts[best] == nil {
			best = best ^ 1
		}
		ans |= (best^path)<<move
		cur = cur.nexts[best]
	}
	return ans
}